/*
You are given two linked lists representing two non-negative numbers.
The digits are stored in reverse order and each of their nodes contain
a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
*/

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/*
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 定义链表结构
typedef struct _LINK_NODE
{
   int data;
   struct _LINK_NODE* next;
}LINK_NODE;

// 创建链表
LINK_NODE* alloca_node(int value)
{
   LINK_NODE* pLinkNode = NULL;
   pLinkNode = (LINK_NODE *)malloc(sizeof(LINK_NODE));

   pLinkNode->data = value;
   pLinkNode->next = NULL;
   return pLinkNode;
}

//删除链表
void delete_node(LINK_NODE** pNode)
{
   LINK_NODE** pNext;
   if(NULL == pNode || NULL == *pNode)
       return ;

   pNext = &(*pNode)->next;
   free(*pNode);
   delete_node(pNext);
}

//链表插入数据
void _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)
{
   if(NULL == *pNode){
       *pNode = pDataNode;
       return 0;
   }

   return _add_data(&(*pNode)->next, pDataNode);
}
void add_data(const LINK_NODE** pNode, int value)
{
   LINK_NODE* pDataNode;
   if(NULL == *pNode)
       return -1;

   pDataNode = alloca_node(value);

   assert(NULL != pDataNode);

   return _add_data((LINK_NODE**)pNode, pDataNode);
}

void _delete_data(LINK_NODE** pNode, int value)
{
   LINK_NODE* pLinkNode;
   if(NULL == (*pNode)->next)
       return -1;

   pLinkNode = (*pNode)->next;
   if(value == pLinkNode->data){
       (*pNode)->next = pLinkNode->next;
       free(pLinkNode);
       return 0;
   }else{
       return _delete_data(&(*pNode)->next, value);
   }
}

// 删除数据
void delete_data(LINK_NODE** pNode, int value)
{
   LINK_NODE* pLinkNode;
   if(NULL == pNode || NULL == *pNode)
       return -1;

   if(value == (*pNode)->data){
       pLinkNode = *pNode;
       *pNode = pLinkNode->next;
       free(pLinkNode);
       return 0;
   }

   return _delete_data(pNode, value);
}

// 查找数据
LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)
{
   if(NULL == pLinkNode)
       return NULL;

   if(value == pLinkNode->data)
       return (LINK_NODE*)pLinkNode;

   return find_data(pLinkNode->next, value);
}

// 打印数据
void print_node(const LINK_NODE* pLinkNode)
{
   if(pLinkNode){
       printf("%d\n", pLinkNode->data);
       print_node(pLinkNode->next);
   }
}

// 统计数据
int count_node(const LINK_NODE* pLinkNode)
{
   if(NULL == pLinkNode)
       return 0;

   return 1 + count_node(pLinkNode->next);
}

int main()
{
   LINK_NODE *l1 = alloca_node(2);
   LINK_NODE *l2 = alloca_node(5);
   LINK_NODE **ll = NULL;
   LINK_NODE **ll2 = NULL;
   ll = (LINK_NODE **)malloc(sizeof(LINK_NODE *));
   ll2 = (LINK_NODE **)malloc(sizeof(LINK_NODE *));
   *ll = l1;
   *ll2 = l2;
   add_data(ll, 4);
   add_data(ll, 3);
   add_data(ll2, 6);
   add_data(ll2, 4);
   print_node(l1);
   int count = count_node(l1);
   printf("\n%d\n\n", count);

   print_node(l2);
   int count2 = count_node(l2);
   printf("\n%d\n", count2);
   return 0;
}
*/
/*
struct ListNode {
    int val;
    struct ListNode *next;
 };

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

}

int main()
{
    struct ListNode *l1 = NULL;
    struct ListNode *l2 = NULL;

    return 0;
}
*/
#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} listNode;

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    listNode *ret = NULL;
    listNode *p = NULL;
    listNode *tmp = NULL;
    int d = 0;

    while (l1 && l2) {
        tmp = (listNode *) malloc(sizeof(listNode));
        tmp->val = (l1->val + l2->val + d) % 10;
        d = (l1->val + l2->val + d) / 10;
        if (!ret) {
            ret = tmp;
            p = ret;
        } else {
            p->next = tmp;
            p = tmp;
        }
        l1 = l1->next;
        l2 = l2->next;
    }
    while (l1) {
        tmp = (listNode *) malloc(sizeof(listNode));
        tmp->val = (l1->val + d) % 10;
        d = (l1->val + d) / 10;
        if (!ret) {
            ret = tmp;
            p = ret;
        } else {
            p->next = tmp;
            p = tmp;
        }
        l1 = l1->next;
    }
    while (l2) {
        tmp = (listNode *) malloc(sizeof(listNode));
        tmp->val = (l2->val + d) % 10;
        d = (l2->val + d) / 10;
        if (!ret) {
            ret = tmp;
            p = ret;
        } else {
            p->next = tmp;
            p = tmp;
        }
        l2 = l2->next;
    }

    if (d && !l1 && !l2) {
        tmp = (listNode *) malloc(sizeof(listNode));
        tmp->val = d;
        p->next = tmp;
        p = tmp;
    }
    p->next = NULL;
    return ret;
}

int main(int argc, char *argv[]) {
    listNode ln1, ln2, ln3, ln4, ln5, ln6;
    listNode *head1, *head2;
    head1 = (listNode *) malloc(sizeof(listNode));
    head2 = (listNode *) malloc(sizeof(listNode));
    ln3.val = 3;
    ln2.val = 4;
    ln1.val = 2;
    head1 = &ln1;
    ln1.next = &ln2;
    ln2.next = &ln3;
    ln3.next = NULL;

    ln4.val = 5;
    ln5.val = 6;
    ln6.val = 4;
    ln4.next = &ln5;
    ln5.next = &ln6;
    ln6.next = NULL;
    head2 = &ln4;

    listNode *p1, *p2;
    p1 = head1;
    while (p1 != NULL) {
        printf("%d\n", p1->val);
        p1 = p1->next;
    }
    p2 = head2;
    while (p2 != NULL) {
        printf("%d\n", p2->val);
        p2 = p2->next;
    }

    listNode *p;
    p = addTwoNumbers(head1, head2);

    p2 = p;
    while (p2 != NULL) {
        printf("%d\n", p2->val);
        p2 = p2->next;
    }

    return 0;
}
